Talk:First undefinable ordinal
does this ordinal...even exist? is it covered anywhere in mathematical literature? and why the heck are we relying on English? FB100Z • talk • 16:47, September 3, 2013 (UTC) About last question - no formal system is able to define what formal system is. Thus we need some sort of "higher order" expressive strength, like English. This ordinal necessarily exists, from countability argument (countably many systems defining countably many ordinals each, thus we have countably many definable ordinals vs. uncountable infinity of ordinals). I don't think mathematical literature ever covered this. LittlePeng9 (talk) 17:07, September 3, 2013 (UTC) \(f_\alpha(n)\) is roughly I(n)? It seems that I(n) works in too paradoxical to be pinned down by any ordinal, because it tries to merge any function (formal or informal) in its set. The speed of doing it is dependent on the human imagination, which is actually the uncharted territory. Ikosarakt1 (talk ^ ) 17:00, September 4, 2013 (UTC) Size Is this ordinal less than \( \)? FB100Z • talk • 18:13, September 10, 2013 (UTC) It is trivially (?) larger than CK ordinal. Reason is that, from very definition of CK, all smaller ordinals are recursive, i.e. defined by some Turing machine. Even weak systems can define all Turing machines (note that they cannot prove all of them define ordinals), so all recursive ordinals are definable. Actually, we can prove this number is admissible, from similar reasoning. LittlePeng9 (talk) 19:00, September 10, 2013 (UTC) Fundamental sequence How would be go about defining (haha) a fundamental sequence for this guy? I would start out with \(\omega_1^\text{DEF}n\) as the least ordinal not definable with at most \(n\) symbols in first-order logic. Hey, wait a second...this looks familiar. FB100Z • talk • 19:59, October 1, 2013 (UTC) :That ordinal would be finite for all \(n\), since there are only finitely many sentences in first-order logic with \(n\) symbols are less, and infinitely many finite ordinals. You probably want something like "\(\omega_1^\text{DEF}n\) is the largest ordinal definable with at most \(n\) symbols in first order logic." :For a fundamental sequence for the smallest absolutely undefinable ordinal (not just the smallest undefinable ordinal in first order logic) I guess I would use something like "\(\omega_1^\text{DEF}n\) is the largest ordinal definable in a LaTeX document using at most \(n\) characters" without restriction to any formal system. This strikes me as pretty vague, though, as one can probably use various tricks to shorten the length of a document describing a particular ordinal, and it can get iffy if a particular document is clear or not. Deedlit11 (talk) 00:13, October 2, 2013 (UTC) ::But LaTeX is itself the formal system, as it has only formally defined number of definitions. The definition of \(\omega_1^\text{DEF}n\) must be defined in the informal sense, and we shall not be able to map this one to anything formalizable. Barry's paradox prevents us to do it. The good idea is using universal languages, and say that \(\omega_1^\text{DEF}n\) is the largest ordinal defined in n symbols, sentences or words on such language. Ikosarakt1 (talk ^ ) 16:40, October 2, 2013 (UTC) :::Eh, LaTeX is not a formal system, it's just a typesetting system. The idea is that you can use informal language to create any ordinal you want. Of course, we could use something like ASCII for that purpose, but that's rather clumsy - LaTeX gives you more expressive power. Of course, that won't affect the size of the smallest absolutely undefinable ordinal. :::I'm not familiar with universal languages. Deedlit11 (talk) 22:47, October 2, 2013 (UTC) :::The universal language, in this case, just a language we use for all our purposes. The example of such a language is English. Probably LaTeX would be really the better choice for \(\omega_1^\text{DEF}n\). Ikosarakt1 (talk ^ ) 22:58, October 2, 2013 (UTC) Is informal language really any stronger than formal language? If we do want to use a human language, I would suggest . Lojban is semantically equivalent to any natural language, but it's based on predicate logic... FB100Z • talk • 04:57, October 3, 2013 (UTC) : In informal language you can define what formal language is, while in formal ones you can't (you can only define things weaker than the whole). LittlePeng9 (talk) 05:43, October 3, 2013 (UTC) ::Yeah, that's basically it. Lojban may be an ideal language for defining all definable ordinals, but I'm a little worried about it being based on predicate logic - might that mean we can't use it to define all possible formal languages? Deedlit11 (talk) 06:03, October 5, 2013 (UTC) :::I'm no linguist, but it seems that all languages are ultimately based on predicate logic. Lojban is not terribly different from any natural language; it just has a cleaned-up syntax and a more direct connection to the underlying formalities. FB100Z • talk • 20:01, November 1, 2013 (UTC) Rayo's function It is certainly false that Ra(n) grows no slower than hypothetical \(f_{\omega_1^\text{DEF}}(n)\), because the entire first order logic is a formal system. Ikosarakt1 (talk ^ ) 16:29, October 2, 2013 (UTC) :The \(\omega_1^\text{DEF}\) referred to in the article is not the smallest absolutely undefinable ordinal, but "merely" the smallest undefinable ordinal in first-order logic. :I'm concerned that "first-order logic" is ambiguous here. There are many theories of first-order logic, see for example. If we choose "first-order logic" to mean first-order arithmetic, we will get a much smaller ordinal than if we took first-order set theory. Perhaps we should switch "first-order logic" to "first-order set theory"? Deedlit11 (talk) 22:53, October 2, 2013 (UTC) ::But then we just speak about FGH ordinal for Rayo's function (Rayo's ordinal). When I created this article, I expected that we are trying to define the limit ordinal for all formal systems in principle, as it would be really significant point for googology. We definitely must have an article about this. Ikosarakt1 (talk ^ ) 23:04, October 2, 2013 (UTC) :::Heh, I should probably hold off making further conclusions on the article until we know what the ordinal is. FB100Z • talk • 05:27, October 3, 2013 (UTC) :This ordinal must be defined informally as the smallest ordinal which we cannot express with n symbols on English, but we run into Berry's paradox. However, if we admit that there is some stronger language than English and refer to English from it, then it is good. :By the way, what's the difference between Berry's paradox and Russell's paradox? Ikosarakt1 (talk ^ ) 15:12, May 20, 2014 (UTC) :If there is any language which can capture all features of English language, then it will also contain all contradictions English has, and likely even more. With analogy to formal systems, if we have an inconsistent theory, then adding additional axioms (making it stronger) will not make it any less inconsistent. :Berry's paradox is one you refer to, which captures paradoxal features of informal languages. Russell's paradox is about "a set of all sets which do not contain themselves", which is paradoxal if one asks if it contains itself. LittlePeng9 (talk) 15:52, May 20, 2014 (UTC)